package leetCode.q31;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Me {
    public int[] res = null;

    public void nextPermutation(int[] nums) {
        /*
            提取出来
            递归深度优先搜索，搜索结果和nums比较，在比较结果为大于的情况下取最小的那个
         */
        int len = nums.length;

        boolean[] visit = new boolean[len];

        Deque<Integer> path = new ArrayDeque<>();

        dfs(nums,visit,path,len);
        nums = Arrays.copyOf(this.res,len);
        for (int re : nums) {
            System.out.println(re);
        }
    }

    private void dfs(int[] nums,boolean[] visit,Deque<Integer> path,int len) {
        //如果遍历完，path比ori大而且比res小，那么就替换res
        if(path.size() == len) {
            //集合转数组
            int[] res = path.stream().mapToInt(Integer::intValue).toArray();

            //比原数组大    取最小的一个
            if(bigger(res, nums, len)){
                if(this.res == null) this.res = res;
                else {
                    if(small(res,this.res,len)){
                        this.res = res;
                    }
                }
            }

            return;
        }

        //没遍历完，向下走一步
        for (int i = 0; i < len; i++) {
//            走过了就跳过
            if (visit[i]) continue;

            visit[i] = true;
            path.add(nums[i]);
            dfs(nums, visit, path, len);
            path.removeLast();
            visit[i] = false;
        }
    }

    public static boolean bigger(int[] a1,int[] a2,int len){
        for(int i=0;i<len;i++){
            if(a1[i]>a2[i]) return true;
            if(a1[i]<a2[i]) return false;
        }
        return false;
    }

    public static boolean small(int[] a1,int[] a2,int len){
        for(int i=0;i<len;i++){
            if(a1[i]<a2[i]) return true;
            if(a1[i]>a2[i]) return false;
        }
        return false;
    }

    public static void main(String[] args) {
        Me me = new Me();
        me.nextPermutation(new int[]{1,2,3});
    }
}
